
struct PrimeMarker {
    marker: Vec<u8>,
}

impl PrimeMarker {
    fn new() -> Self {
        Self {
            marker: Vec::new(),
        }
    }
    fn test(&self, x: u64) -> bool {
        let id = (x / 8) as usize;
        let offset = (x % 8) as usize;
        if self.marker.len() <= id {
            false
        } else {
            (self.marker[id] >> offset) & 1 == 1
        }
    }

    fn set(&mut self, x: u64) {
        let id = (x / 8) as usize;
        let offset = (x % 8) as usize;
        if self.marker.len() <= id {
            self.marker.resize(id + 1, 0);
        }
        self.marker[id] |= 1 << offset;
    }
}

pub fn goldbach_conjecture() -> u64 {
    let mut marker = PrimeMarker::new();
    let mut primes = Vec::new();
    let mut ans = Vec::new();
    for i in 2.. {
        if marker.test(i) == false {
            primes.push(i);
        }
        for &j in &primes {
            marker.set(i * j);
            if i % j == 0 {
                break;
            }
        }
        if i % 2 == 1 && marker.test(i) == true {
            let valid = (1..).map(|j| 2 * j * j)
            .take_while(|&x| x < i)
            .any(|x| marker.test(i - x) == false);
            if valid == false {
                ans.push(i);
                if ans.len() == 2 {
                    break;
                }
            }
        }
    }
    ans.iter().sum()
}
